# coding=utf-8

from graph import *

BD_SIZE = 16
MOVE_OFFSETS = [(-1, -2), (-1, 2), (-2, -1), (-2, 1),
                (1, -2), (1, 2), (2, -1), (2, 1)]


def pos_to_coord(row, col, bd_size):
    """
    计算坐标
    :rtype: int
    :param row: 横坐标
    :param col: 纵坐标
    :param bd_size: 棋盘大小
    :return: 坐标
    """
    return (row * bd_size) + col


def gen_legal_moves(row, col, bd_size):
    new_moves = []
    for x, y in MOVE_OFFSETS:
        new_row = row + x
        new_col = col + y
        if 0 <= new_row < bd_size and 0 <= new_col < bd_size:
            new_moves.append((new_row, new_col))
    return new_moves


def knight_graph(bd_size):
    g = BFSGraph()
    for row in xrange(bd_size):
        for col in xrange(bd_size):
            node_coord1 = pos_to_coord(row, col, bd_size)
            for x, y in gen_legal_moves(row, col, bd_size):
                node_coord2 = pos_to_coord(x, y, bd_size)
                g.add_edge(node_coord1, node_coord2)
    return g


if __name__ == '__main__':
    knight_g = knight_graph(BD_SIZE)
    knight_g.bfs(0)
    print knight_g.travers(255)
